import random


class Sort:
    def __init__(self, n):
        """
        创建一个长度为n的待排序列表
        """
        self.len = n  # 待排序列表长度
        self.arr = [0] * n
        for i in range(self.len):  # 随机生成待排序列表
            self.arr[i] = random.randint(0, 99)

    def partition(self, left, right):
        """
        快速排序一趟
        """
        arr = self.arr
        k = i = left
        random_pos = random.randint(left, right)  # 避免陷入最坏时间复杂度
        arr[random_pos], arr[right] = arr[right], arr[random_pos]
        for i in range(left, right):  # 某个位置的值小于分隔值，与k所指向位置交换
            if arr[i] < arr[right]:
                arr[i], arr[k] = arr[k], arr[i]
                k += 1
        arr[k], arr[right] = arr[right], arr[k]
        return k

    def qucik_sort(self, left, right):
        """
        快速排序
        """
        if left < right:
            piovt = self.partition(left, right)
            self.qucik_sort(left, piovt - 1)
            self.qucik_sort(piovt + 1, right)


if __name__ == '__main__':
    # 快速排序
    count = 15
    my_sort = Sort(count)
    print(f'原待排序列表：{my_sort.arr}')
    my_sort.qucik_sort(0, count - 1)
    print(f'快速排序后列表为：{my_sort.arr}')
